Many functions desired by a user of a programmable logic device may be implemented by configuring the device to form a finite state machine. A finite state machine may be implemented in a programmable logic device in a number of ways. For example, each state may be assigned to a flip-flop within the programmable logic device in a technique known as “one-hot” encoding. In such a method, the number of states equals the required number of flip-flops. Thus, as the complexity of the state machine increases, the required number of flip-flops may become excessive. To reduce the required number of flip-flops for a complex design, the states may be binary encoded such that the required number of flip-flops equals Log2(number of states).
Even with the use of binary encoding, the logic required to perform the state transition burdens the resources of a programmable logic device. In particular, many useful state machines have a “program-like” behavior in which successive states are either predetermined (linear sequence) or selected from a choice of two or more possibilities (branching). Implementing such a state machine can require a significant amount of logic resources. For example, in a complex programmable logic device (CPLD), each logic block provides a limited number of product terms and a limited number of flip-flops. A particular state machine implementation may require multiple logic blocks because it has more product terms than are available from a single logic block. Moreover, the limited number of flip-flops in a single logic block may be too small to enable one-hot encoding of such a state machine.
Accordingly, there is a need in the art for an improved programmable logic devices that facilitates the implementation of state machines.